（归并 逆序对性质）小朋友排队
题目 小朋友排队
思路分析
关于冒泡排序
冒泡排序是基于逆序对的思想，有多少个逆序对就需要交换多少次。他是贪心的思想，因为每次交换相邻的两个
元素最多使逆序对减少1。
有k个逆序对的数组：
1、交换次数至少是k；
2、在冒泡排序中每次必然是交换（Ai ，Ai+1），当Ai > Ai+1时，因此必然使逆数（逆序对数量）减一。
关于本题
样例：3 2 5 4 1
对于2号，假设前面有k1个比他大的，后面有k2个比他小的，那么2号的移动次数k >= k1 + k2
可否取等号？假设每个小朋友的移动次数都是k1和k2组成，all_sum(移动次数) >= 2k(k为逆数)
所以全局取得最小值时没有多余的操作，即取等号，2的移动次数 = k1 + k2
个人觉得稍微容易理解的方式就是：当前数前面有多少个比我大的，都要和我交换一次位置，后面比我小的也要 和我交换位置，也就是上述的k1 + k2
所以本题就变成了求每个数的k1 + k2，即前面比我大和后面比我小的和
==
如果一个小朋友交换的次数过大，那么肯定是最坏的情况，需要尽可能使每个小朋友交换的次数最少，而每个小朋友最少的交换次数就是将前面比他大的和后面比他小的都交换，就得到上面的结论。
归并排序方式
需要注意的一点是，逆序对的数量可以直接照着后面的数比当前数小来计算参考逆序对数量
但是根据上面的分析，需要求的当前点的k1和k2，所以需要进行更细致的情况划分。
假定逆序对的数量为k个，k1和k2的总和是2k个。
关于代码的一点踩坑，刚开始想直接sum数组中记录每个身高的的左右k1、k2之和，而不是记录第几个孩子的左右k1、k2之和。但是经过代码发现只能通过3个样例，猜想是因为孩子的身高可能相同，这样就等于人为改变了输入的数据。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, s[N];
struct Stu
{
int id, h;
}stus[N], tmp[N];
void merge(int l, int r)
{
if (l >= r)
return;
int mid = l + r >> 1, i = l, j = mid + 1, k = 0;
merge(l, mid), merge(mid + 1, r);
while (i <= mid && j <= r)
{
// 也可以第一个判断找左边情况第二个判断找右边情况
// 但是第二个判断找右边情况时 即找右边比当前数严格小的情况
// 会发现区间属于[mid + 1, j]，但是j前面是否等于当前数需要特判 不能直接认定严格小
if (stus[i].h <= stus[j].h)
{
// 找一个数的右边情况
// 此时右半部分[mid + 1, j)的数都比q[i]严格小
// 这里的顺序不能颠倒 否则更新sum使用到的i已经变了！！
s[stus[i].id] += j - mid - 1;
tmp[k++] = stus[i++];
}
else
{
// 找一个数的左边情况
// 此时左半部分[i, mid]的数都比q[j]严格大
s[stus[j].id] += mid - i + 1;
tmp[k++] = stus[j++];
}
}
// 下面两个while用于补充特殊情况
while (i <= mid)
{
// j已经走完了但是i还没有走完 说明左半部分从i开始到mid的区间内的数都比右半部分严格大
// 此时可以用 j - mid - 1 + 1 - 1 ==> j - mid - 1
// 因为上面的while走完后j处在r+1的位置 需要在减去1
// 更直白的方式应该用r - mid 即右半部分的个数
s[stus[i].id] += r - mid;
tmp[k++] = stus[i++];
}
while (j <= r)
// j有剩余说明i前面都比他小 所以不需要更新
tmp[k++] = stus[j++];
for (int i = l, k = 0; i <= r;)
stus[i++] = tmp[k++];
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int h;
cin >> h;
stus[i] = {i, h};
}
merge(0, n - 1);
long long res = 0;
for (int i = 0; i < n; i++)
res += (long long)s[i] * (1 + s[i]) / 2;
cout << res;
return 0;
}
同类题型
视频讲解
⬅️ （70分 dp+贪心）倍数问题 🏠 00-刷题理模型 ➡️ 填充
💬 评论